package com.justnow.offer;

public class Solution02 {

    /**
     * 方法一：递归的方法来解决
     * @param n
     * @return
     */
    public int jump01(int n) {
        if (n <= 2)
            return n;
        return jump01(n-1) + jump01(n-2);
    }


    /**
     * 方法二：动态规划的思想
     * 状态转移方程是：dp[i] = dp[i-1] + dp[i-2]
     * https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/solution/javaqing-wa-tiao-tai-jie-he-fei-bo-na-qi-shu-lie-t/
     * @param n
     * @return
     */
    public int jump02(int n) {
        if (n <= 1)
            return 1;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    /**
     * 方法三：基于循环的内容
     * https://www.cnblogs.com/liangchao/archive/2012/09/17/2689631.html
     *
     * 因为递归的计算过程，可以将其每个计算的过程当做一个树的节点。那么我们现在从下往上
     *
     * @param args
     */

    /**
     * 方法三：基于循环的内容
     * https://www.cnblogs.com/liangchao/archive/2012/09/17/2689631.html
     *
     * 因为递归的计算过程，可以将其每个计算的过程当做一个树的节点。那么我们现在从下往上,这样反而会减少计算的次数
     * f(3) = f(2) + f(1),
     * f(4) = f(3) + f(2),
     * f(5) = f(4) + f(3),
     * 。。。。
     * f(n-1) = f(n-2) + f(n-3),
     * f(n) = f(n-1) + f(n-2)
     * @param n
     * @return
     */
    public int jump03(int n) {
        if (n < 2)
            return n;
        int jumpNMinusOne = 1;
        int jumpNMinusTwo = 2;
        int jumN = 0;
        for (int i = 3; i <= n; i++) {
            jumN = jumpNMinusTwo + jumpNMinusOne; //可以把这个看做f(3) = f(2) + f(1)
            //我们在计算下一步的话，会用到上一步的f(2) 和 上一步的f(3),所以在这里直接进行替换！
            jumpNMinusOne = jumpNMinusTwo;
            jumpNMinusTwo = jumN;
        }
        return jumN;
    }
    public static void main(String[] args) {
        Solution02 solution2 = new Solution02();
        byte[] bytes = new byte[1024 * 1024];
        int s1 = solution2.jump01(8);
        int s2 = solution2.jump02(8);
        int s3 = solution2.jump03(8);
        System.out.println(s1);
        System.out.println(s2);
        System.out.println(s3);
    }
}
